﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0077_AllPathsSourceTarget : IAlgorithm
    {
        // 797. 所有可能的路径

        // 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
        // 二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
        // 译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。

        // 提示：
        //  n == graph.length
        //  2 <= n <= 15
        //  0 <= graph[i][j] < n
        //  graph[i][j] != i（即，不存在自环）
        //  graph[i] 中的所有元素 互不相同
        //  保证输入为 有向无环图（DAG）

        public void Test()
        {
            // 算法参数定义
            //[[1,2],[3],[3],[]]
            //[[4,3,1],[3,2,4],[],[4],[]]
            //[[2],[],[1]]
            var graph = new int[][] { new int[] {2 }, new int[] {  }, new int[] { 1} };
            // 算法执行与打印
            var res = AllPathsSourceTarget(graph);
            foreach (var item in res)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public IList<IList<int>> AllPathsSourceTarget(int[][] graph)
        {
            var res = new List<IList<int>>();
            DFS(graph, new List<int>() { 0 }, 0, res);
            return res;
        }
        private void DFS(int[][] graph, List<int> temp, int last, IList<IList<int>> res)
        {
            if (temp.Last() == graph.Length - 1)
                res.Add(temp.ToArray());
            else
                for (int i = 0; i < graph[last].Length; i++)
                {
                    temp.Add(graph[last][i]);
                    DFS(graph, temp, graph[last][i], res);
                    temp.RemoveAt(temp.Count - 1);
                }
        }
    }
}
